package com.lhcai.lc.category.prefixsum;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. 和为K的子数组
 * 前缀和
 *
 * @author liuhuaicai
 * @since 2024-10-16 21:48
 */
public class Lc560 {
    public static void main(String[] args) {
        Lc560 lc560 = new Lc560();
        System.out.println(lc560.subarraySum(new int[]{1, 2, 3}, 3));
    }

    // 前缀和
    // pre[i]为前i个元素之和
    // 则有 pre[j] + arr [j+1] + ... + arr[i] = pre[i] 即 pre[i] - pre[j] =  arr [j+1] + ... + arr[i]
    // 假设 pre[i] - pre[j] = k ,则arr [j+1] + ... + arr[i] = k 即以j+1开头，i结尾的子串 符合条件
    // 也即 pre[i] - k = pre[j]
    // 我们将所有符合条件的进行统计 ，即为结果
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        // 当前前缀和
        int pre = 0;
        // 记录前缀和的值出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        // // 初始化前缀和为0的次数为1，即自身符合条件
        map.put(0, 1);
        // 从左往右遍历的时候，可以保证 j < i，不会出现重复
        for (int i = 0; i < nums.length; i++) {
            // 获得pre[i]
            pre += nums[i];
            // 有符合的pre[j],有的话，则以j+1开头，i结尾的子串 符合条件
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            // 当前pre存入map
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    // 暴力解法
//    public int subarraySum(int[] nums, int k) {
//        int count = 0;
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            // 以 i 为终点，求它包含所有的子串
//            for (int j = i; j >= 0; j--) {
//                sum += nums[j];
//                // 子串之和为k
//                if (sum == k) {
//                    count++;
//                }
//            }
//            sum = 0;
//        }
//        return count;
//    }
}
